// run: $exec < input
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
struct node{
	int l, r, ll, rr, p, len;
	node () {}
	node (int l, int r, int ll, int rr) :l(l), r(r), ll(ll), rr(rr){}
}tr[500000];
int n, q;
char str[300000];
void push_up(int p){
	int tt=min(tr[p<<1].ll, tr[p<<1|1].rr);
	tr[p].ll=tr[p<<1].ll+tr[p<<1|1].ll-tt;
	tr[p].rr=tr[p<<1].rr+tr[p<<1|1].rr-tt;
}

void init(int p, int l, int r){
	tr[p]=node (l, r, 0, 0);
	if (l==r){
		if (str[l-1]=='(') tr[p].ll=1;
		else tr[p].rr=1;
		return;
	}
	init(p<<1, l, (l+r)/2);
	init(p<<1|1, (l+r)/2+1, r);
	push_up(p);
}

node find(int p, int l, int r){
	if (l>r) return node (0, 0, 0, 0);
	if (tr[p].l==l && tr[p].r==r) return tr[p];
	if (r<=tr[p<<1].r) return find(p<<1, l, r);
	else if (l>=tr[p<<1|1].l) return find(p<<1|1, l, r);
	else{
		node a=find(p<<1, l, tr[p<<1].r);
		node b=find(p<<1|1, tr[p<<1|1].l, r);
		int tt=min(a.ll, b.rr);
		node tmp=node(0, 0,a.ll+b.ll-tt, a.rr+b.rr-tt);
		return tmp;
	}
}

void update_pt(int p, int x){
	if (tr[p].l==x && tr[p].r==x){
		if (str[x-1]=='('){
			tr[p].ll=1;
			tr[p].rr=0;
		}
		else {
			tr[p].rr=1;
			tr[p].ll=0;
		}
		return;
	}
	if (x<=tr[p<<1].r) update_pt(p<<1, x);
	else update_pt(p<<1|1, x);
	push_up(p);
}

int main(){
	int t;
	scanf("%d", &t);
	while(t--){
		scanf("%d%d", &n, &q);
		scanf("%s", str);
		init(1, 1, n);
		for (int i=0;i<q;i++){
			int com, x, y, k;
			scanf("%d", &com);
			if (com==1){
				scanf("%d", &x);
				if (str[x-1]=='(') str[x-1]=')';
				else str[x-1]='(';
				update_pt(1, x);
			}
			else{
				scanf("%d%d%d", &x, &y, &k);
				node tmp=find(1, x, y);
				if (tmp.ll+tmp.rr<k){
					printf("-1\n");
					continue;
				}
				int l=x, r=y, pos=100000000;
				while(l<=r){
					int mid=(l+r)/2;
					node tmp1=find(1, x, mid);
					node tmp2=find(1, mid+1, y);
					int tt=tmp1.ll+tmp1.rr-min(tmp1.ll, tmp2.rr);
					if (tt<k)
						l=mid+1;
					else{
						r=mid-1;
						pos=min(pos, mid);
					}
				}
				printf("%d\n", pos);
			}
		}
	}
	return 0;
}
